package 动态规划;

import java.util.Scanner;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-22 19:23
 **/
public class 二维数组dp路径个数 {
    /**
     *问题描述
     *
     * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
     *
     * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
     *
     * 问总共有多少条不同的路径？
     *
     *
     * @param args
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m=scanner.nextInt();
        int n=scanner.nextInt();
        int result = f(m, n);
        System.out.println(result);

    }

    public static int f(int m,int n){
        int[][] dp = new int[m][n];
        int i,j;
        /**
         * 想象一下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
         *
         * 一种是从 (i-1, j) 这个位置走一步到达
         *
         * 一种是从(i, j - 1) 这个位置走一步到达
         */
        //dp[i][j]=dp[i-1][j]+dp[i][j-1]
        //边界的初始化
        for(i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(j=0;j<n;j++){
            dp[0][j]=1;
        }
        for(i=1;i<m;i++){
            for(j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        char[] chars = {'h','e','l'};
        String s = String.valueOf(chars);
        System.out.println(String.valueOf(chars));
        return dp[m-1][n-1];





    }

}
